Search for: All records

A $k$-factorization of the complete $t$-uniform hypergraph $K^{(t)}_{v}$ is an $H$-decomposition of $K^{(t)}_{v}$ where $H$ is a $k$-regular spanning subhypergraph of $K^{(t)}_{v}$. We use nauty to generate the 2-regular and 3-regular spanning subhypergraphs of $K^{(3)}_v$ for $v\leq 9$ and investigate which of these subhypergraphs factorize $K^{(3)}_v$ or $K^{(3)}_v-I$, where $I$ is a 1-factor. We settle this question for all but two of these subhypergraphs. 

A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $T$ with $n$~edges, it is conjectured that there exists a labeling $f\colon V(T) \to \{0,1,\ldots,n\}$ such that the set of induced edge labels $\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$ is exactly $\{1,2,\ldots,n\}$. We extend this concept to allow for multigraphs with edge multiplicity at most~$2$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $G$ with $n$~edges is a one-to-one function $f\colon V(G) \to \{0,1,\ldots,n\}$ such that the multiset of induced edge labels is comprised of two copies of each element in $\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$ and, if $n$ is odd, one copy of $\bigl\{ \lceil n/2 \rceil \bigr\}$. When $n$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $n \not\equiv 1 \pmod{4}$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $2$-fold graceful. 

Let $G$ be one of the two multigraphs obtained from $K_4-e$ by replacing two edges with a double-edge while maintaining a minimum degree of~2. We find necessary and sufficient conditions on $n$ and $\lambda$ for the existence of a $G$-decomposition of $^{\lambda}K_n$. 

Consider the multigraph obtained by adding a double edge to $K_4-e$. Now, let $D$ be a directed graph obtained by orientating the edges of that multigraph. We establish necessary and sufficient conditions on $n$ for the existence of a $(K^{*}_{n},D)$-design for four such orientations.